https://www.acmicpc.net/problem/2839문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)출력상근이..
전체 글
항공대 알고리즘 동아리 Koala 🥰https://www.acmicpc.net/problem/15654 문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.답안 코드N,M = map(int,input().split())arr = list(map(in..
접근 방법이미지는 R X C의 2차원 픽셀, 필터의 크기는 3 X 3이고 이미지의 중앙값을 통해 판단Brute Force로 조금은 무식하게 시도해보자.필터의 크기가 3 X 3 이므로, 9개의 값을 배열에 저장 후 중간값을 구해 해당 값을 T(임계값)와 비교이를 2중 반복문으로 R-2, C-2 까지 반복해서 비교#include #include using namespace std;int main() { int R, C; cin >> R >> C; int A[R][C]; for (int i = 0; i > A[i][j]; } } int T; cin >> T; int count = 0; for (int i = 0; i = T) count++; ..
https://www.acmicpc.net/problem/1206알고리즘 유형- 브루트포스 알고리즘문제송유진은 길거리에서 사람들에게 설문조사를 하고 있다. 설문조사에는 N개의 문항이 있고, 설문에 응한 사람은 각 문항을 0보다 크거나 같고, 10보다 작거나 같은 정수로 대답해야 한다.설문조사를 모두 마친 후 유진이는 각 문항의 평균 점수 소수점 셋째 자리에서 자른 값을 보고서 종이에 적고 사무실로 돌아왔다. 예를 들어, 어떤 문항에 각 사람이 점수를 4, 6, 10점으로 대답했다면, 평균 점수는 6.666이다. 이제 설문조사 결과를 보고해야 하는데, 문제가 하나 생겼다. 평균 점수만 알고 있기 때문에, 설문조사에 참여한 사람의 수를 알 수 없다는 점이다.각 문항의 평균 점수가 주어진다. 이때 설문조사에 ..
문제https://www.acmicpc.net/problem/12101풀이* 첫째줄에 정수 n과 k가 주어진다.* n을 1, 2, 3의 합으로 나타내는 방법 중 사전 순으로 k번째에 오는 것을 출력해야 한다. (k번째로 오는 식이 없으면 -1 출력)1. 정수 n과 k를 입력받는다.2. DFS를 이용해 모든 조합을 생성하고, 조합이 완성되면 +로 문자열을 연결해 result 리스트에 저장한다.3. k번째 경우를 반환하는데, 없으면 -1을 출력한다. 코드 및 설명
문제 https://www.acmicpc.net/problem/10974 Algorithm 깊이 우선 탐색(DFS)과 백트래킹을 이용하여 모든 가능한 조합을 탐색한다.현재까지의 순열을 temp 리스트에 저장한다.모든 숫자를 하나씩 시도하며, 이미 사용된 숫자는 제외한다.순열이 완성되면 출력하고, 다른 가능한 순열을 찾기 위해 마지막 숫자를 제거한다(백트래킹). Coden = int(input())temp = []def dfs(): if len(temp) == n: print(*temp) return for i in range(1, n + 1): if i not in temp: temp.append(i) dfs()..
문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)풀이K보다는 작으면서 가장 큰 동전을 선택한 다음, 그 다음으로 큰 동전을 선택하면서 현재 채운 값과 사용한 동전 수를 업데이트하며 K를 모두 채웠을 때 출력한다.코드N, K = map(int, input().split())coins = [int(..
문제https://www.acmicpc.net/problem/2525풀이* 첫째줄에는 현재 시간(시간, 분)이, 둘째 줄에는 요리하는데 필요한 시간이 주어진다.* 현재시간에서 오븐 구이가 끝나는 시간을 출력해야 한다.1. 자연수 h, m 그리고 d를 입력받는다.2. 끝나는 시간을 계산하기 위해 변수 x를 만들고, 분으로 변환한 후 범위 내 출력을 생각해 1,440으로 나눈다.3. 시와 분을 구하기 위해 필요한 연산을 하고, 제시한 대로 출력한다. 코드 및 설명
문제 https://www.acmicpc.net/problem/10872 Algorithm반복문을 사용해서 1부터 N 까지 곱해준다. Coden = int(input())result = 1if n > 0: for i in range(1, n+1): result *= iprint(result)
문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.풀이N부터 시작하는 위치를 deque에 넣고, visited배열로 각 위치의 방문 여부(-1로 초기화)와 최소 시간을 업데이트 해나간..
문제 & 링크https://www.acmicpc.net/problem/1916 풀이1. 정점(도시)의 개수 n과 간선(버스)의 개수 m을 입력받는다.2. 그래프를 인접 리스트의 형태로 저장한다.3. 최단 거리 배열인 cost를 큰 값으로 초기화한다.4. 다익스트라 알고리즘을 사용하여 최단 거리를 탐색한다.5. 우선 순위 큐를 사용해서 최소 비용부터 탐색한다.6. 모든 인접 정점을 처리하며 최단거리를 갱신한다. 코드#include #include #include #include using namespace std;int cost[1001];vector> V[1001];void dijkstra(int a) { priority_queue, vector>, greater>> pq; pq.push(ma..
문제 https://www.acmicpc.net/problem/17608 Algorithm첫 줄에 막대기의 개수 n을 입력 받는다둘째 줄부터 n개의 막대기 길이를 입력받는다.스택의 마지막을 1로 설정하여 마지막 막대기보다 긴 막대기가 있으면 count += 1을 하고 막대기의 길이를 가장 긴 막대기로 새로 저장한다. Codeimport sysinput = sys.stdin.readlineN = int(input())stack = []for _ in range(N): stack.append(int(input()))last = stack[-1]count = 1for i in reversed(range(N)): if stack[i] > last: count += 1 ..